package com.example.algorithm;

/**
 * 最小路径和
 *
 * @author
 * @DATE 2024/6/30
 **/
public class LiKou64 {

    public static void main(String[] args) {
        int[][] grid = {{1,3,1},{1,5,1},{4,2,1}};
        System.out.println(minPathSum(grid));
    }

    // 利用动态规划
    /**
     * 从左上角出发，到达坐标(i,j)的路径数字和最小值。
     * 令 f[i][j]表示从左上角到坐标(i,j)的路径数字和最小值，原问题即可被划分为多个求最优值的子问题，
     * 且由于每次只能向下或向右移动一步，因此 f[i][j]的取值由f[i-1][j]和f[i][j-1]的值决定，即符合「最优子结构原则」。
     * 进一步验证，可以发现， f[i][j] 的取值与f[i-1][j]和f[i][j-1]所对应的具体路径无关，因此符合「无后效性」。
     * 则dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
     * 这里需要注意边界问题，比如第一行和第一列，只能向下或者向右运动。
     *
     * @param grid
     * @return
     */
    public static int minPathSum(int[][] grid) {
        // 判断数据是否为空
        if(grid==null||grid.length==0||grid[0].length==0){
            return 0;
        }
        // 行
        int rows = grid.length;
        // 列
        int cols = grid[0].length;
        int[][] dp = new int[rows][cols];
        // 左上角元素值
        dp[0][0] = grid[0][0];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if(i==0 &&j==0){
                    continue;
                }
                if(i!=0&&j==0){
                    // 第1列
                    dp[i][0] = dp[i-1][0]+grid[i][0];
                }else if(i==0&&j!=0){
                    // 第一行
                    dp[0][j] = dp[0][j-1]+grid[0][j];
                }else{
                    // 找出向下或向右的最小值+当前值
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
                }
            }
        }
        return dp[rows-1][cols-1];
    }

}
